package org.hot100_3;

public class leetcode124 {

    int maxSum = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
       getMaxSum(root);
       return maxSum;
    }

    private int getMaxSum(TreeNode root){
        if (root==null){
            return 0;
        }

        int left = Math.max(0,getMaxSum(root.left));
        int right = Math.max(0,getMaxSum(root.right));

        int currPathSum = left+right+root.val;

        maxSum=Math.max(maxSum,currPathSum);

        return Math.max(left,right)+root.val;
    }





    //错误
    private int getMaxPathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }

        int leftSum = getMaxPathSum(root.left, sum);

        int rightSum = getMaxPathSum(root.right, sum);

        sum += root.val;

        maxSum = Math.max(maxSum, leftSum + rightSum + root.val);

        return sum;
    }

}
